public class BinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode leftNode;
        public TreeNode rightNode;
        public TreeNode(char val){
            this.val=val;
        }
    }
    //创建二叉树；
    public TreeNode create(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
       A.leftNode=B;
       A.rightNode=C;
       B.leftNode=D;
       B.rightNode=E;
       C.leftNode=F;
       C.rightNode=G;
       E.rightNode=H;
       return A;
    }

    //前序遍历二叉树；
    public void preOrder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.leftNode);
        preOrder(root.rightNode);
    }
    //中序遍历二叉树；
    public void MiddleOrder(TreeNode root){
        if(root==null){
            return;
        }
        MiddleOrder(root.leftNode);
        System.out.print(root.val+" ");
        MiddleOrder(root.rightNode);
    }
//后续遍历二叉树；
    public void LastOrder(TreeNode root){
        if(root==null){
            return;
        }
        LastOrder(root.leftNode);
        LastOrder(root.rightNode);
        System.out.print(root.val+" ");
    }
//获取二叉树中结点的个数；
    //方法一：遍历法；
    int usedSize=0;
    public int getTreeNdoeCount(TreeNode root){
        if(root==null){
            return 0;
        }
        usedSize++;
        getTreeNdoeCount(root.leftNode);
        getTreeNdoeCount(root.rightNode);
        return usedSize;
    }
    //方法二：子问题思路：
    public int getTreeNodeCount2(TreeNode root){
        if(root==null){
            return 0;
        }
        return getTreeNodeCount2(root.leftNode)+getTreeNodeCount2(root.rightNode)+1;
    }
    //获取子叶子结点的个数；
    //方法一：遍历法；
    int leafCount1=0;
    public int getLeafNodeCount1(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.leftNode==null&&root.rightNode==null){
            leafCount1++;
        }
        getLeafNodeCount1(root.leftNode);
        getLeafNodeCount1(root.rightNode);
        return leafCount1;
    }
    //方法二：子问题思路；
    public int getLeafNodeCount2(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.leftNode==null&&root.rightNode==null){
            return 1;
        }
        return getLeafNodeCount2(root.leftNode)+getLeafNodeCount2(root.leftNode);
    }
    //获取二叉树的第K层结点个数；
    public int getK(TreeNode root, int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getK(root.leftNode,k-1)+getK(root.rightNode,k-1);
    }
    //获取二叉树的高度；
    public int getTreeNodeHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight=getTreeNodeHeight(root.leftNode);
        int rightHeight=getTreeNodeHeight(root.rightNode);
        return Math.max(leftHeight,rightHeight)+1;
    }
    //判断二叉树中是否存在值为value的值，若存在则返回该节点；
    public TreeNode find(TreeNode root,int val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        TreeNode ret=find(root.leftNode,val);
        if(ret!=null){
            System.out.println("存在该节点");
            return ret;
        }
        TreeNode ret1=find(root.rightNode,val);
        if(ret1!=null){
            System.out.println("找到了");
            return ret1;
        }
        return null;
    }
}

